package StringSearchingAlgorithm;

import java.util.Arrays;

/**
 * KMP 字符串搜索算法
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class KMP {
    public static void main(String[] args) {
        int match = match("abcdef", "issip");
        System.out.println(match);
    }

    static private int match(String s, String p){
        int j = 0;
        int i = 0;
        int[] next = buildNextArr(p);
        while(j < p.length() && i < s.length()) {
            if(0 > j || s.charAt(i) == p.charAt(j)){
                i++;
                j++;
            }else{
                j = next[j];
            }
        }
        return i - j;
    }
    static private int[] buildNextArr(String p){
        int[] next = new int[p.length()];
        int t = -1;
        int j = 0;
        next[0] = t;
        while (j < p.length()-1){
            if(0 > t || p.charAt(t) == p.charAt(j)){
                t++;
                j++;
                next[j] = t;
            }else{
                t = next[t];
            }
        }
        return next;
    }
}
